package missingNumber;

public class Solution {
    public int missingNumber(int[] nums) {
        // 丢失的数字
        // 数学
//        int n = nums.length;
//        int total = n*(n+1)/2;
//        int sum = 0;
//        for (int i = 0; i < n; i++) {
//            sum+=nums[i];
//        }
//        return total - sum;

        // 位运算
//        int xor = 0,n = nums.length; // 0^a = a;
//        for (int i = 0; i <= n; i++) {
//            xor^=i;
//        }
//        for (int i = 0; i < n; i++) {
//            xor^=nums[i];
//        }
//        return xor;

        // 二分查找
        // 因为数组已经排序了 可以使用二分查找
        int l = 0,r = nums.length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if( nums[mid] == mid ) {
                l++;
            }else {
                r--;
            }
        }
        return l;
    }
}
